/** \file    lru.h
  * \brief   Organizes least-recently-used list for implementation of some cache.
  * \date    2002, 2003
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/include/xtd/lru.h,v 1.1 2005/04/04 04:10:16 cscom1r4 Exp $
  */

#ifndef _lru_h_
#define _lru_h_

#include <list>
#include <algorithm>
#include <memory>
#include <stdexcept>
#include <string>
#include <assert.h>

namespace xtd {

/*
 * template parameters meaning
 * T - type of objects stored in the LRU, it should define
 *		key_type
 *		key_type key() const      or  const key_type & key() const
 *		value_type
 *		const value_type & value() const
 *		resource_type
 *		resource_type resource() const
 *		//static resource_type resource(const value_type &)
 */

template <class T>
class lru_elem_ptr: public std::auto_ptr<T> {
public:
	typedef std::auto_ptr<T> superclass;
	typedef typename T::key_type key_type;
public:
	explicit lru_elem_ptr(T * ptr = 0) : 
		superclass(ptr), _ref_count(0) {}
	lru_elem_ptr(const lru_elem_ptr & r) :	_ref_count(0) 
		{ assert(r.get() == 0 && r.free()); }
	~lru_elem_ptr()
		{ assert(free()); }

	//transfers ownership from one object to another
	lru_elem_ptr & operator = (lru_elem_ptr & r) {
		assert(get() == 0 && free());
		superclass::operator = (r);
		_ref_count = r._ref_count;
		r._ref_count = 0;
		return *this;
	}
	///comparison based on key
	friend bool operator == (const lru_elem_ptr & l, const lru_elem_ptr & r) {
		if (l.get() == 0 || r.get() == 0)
			return false;
		return l->key() == r->key();
	}
	friend bool operator == (const key_type & l, const lru_elem_ptr & r) {
		if (r.get() == 0)
			return false;
		return l == r->key();
	}
	friend bool operator == (const lru_elem_ptr & l, const key_type & r) {
		if (l.get() == 0)
			return false;
		return l->key() == r;
	}

	void add_ref()
		{ ++_ref_count; }
	void release()
		{ --_ref_count; assert(_ref_count >= 0); }
	bool free() const
		{ return _ref_count == 0; }

private:
	int _ref_count;
};

template <class T>
class lru {
public:
	typedef typename T::key_type		key_type;
	typedef typename T::value_type		value_type;
	typedef typename T::resource_type	resource_type;

public:
	lru(resource_type total_resources = 0) : 
		_total_resources(0), _rest_resources(total_resources)
		{}

	void add_resources(resource_type inc)
	{ 
		_total_resources += inc;
		_rest_resources += inc;
		free_not_find_room();
	}

	void total_resources(resource_type new_total)
		{ add_resources(new_total - _total_resources); }
	resource_type total_resources() const
		{ return _total_resources; }

	void purge() 
	{
		resource_type safe_total = _total_resources;
		total_resources(0);
		total_resources(safe_total);
	}

	template <class P>
	void purge_if(const P & p) 
	{
		for (list_t::iterator i = _list.begin(); i != _list.end(); ) 
		{
			if (i->free() && p(**i)) {
				_rest_resources += i->get()->resource();
				i = _list.erase(i);
			}
			else
				++i;
		}
	}

	///function is called if the object was not in the list (here this is not tested)
	///function places the object (allocated by new) to the front (or tail) of the list, and
	///it may happen that several objects from tail of list will be freed
	void take(T * t, bool add_ref = false, bool front = true)
	{
		list_elem_t * e;
		if (front) {
			_list.push_front(list_elem_t());
			e = &_list.front();
		}
		else {
			_list.push_back(list_elem_t());
			e = &_list.back();
		}
		e->reset(t);
		if (add_ref)
			e->add_ref();
		_rest_resources -= t->resource();
		free_not_find_room();
	}

	///orders to destroy stored object even if resources are available
	void unload(const key_type & key)
	{
		list_t::iterator i;
		i = std::find(_list.begin(), _list.end(), key);
		if (i == _list.end())
			return;
		_rest_resources += i->get()->resource();
		_list.erase(i);
	}

	bool empty() const
		{ return _list.empty(); }

	///returns the value of object stored in the list and found by key, 
	///increases its ref. counter
	///\return 0 if no such object (key) exists
	const T * get(const key_type & key, bool front = true) throw()
	{
		list_t::iterator i;
		i = std::find(_list.begin(), _list.end(), key);
		if (i != _list.end()) {
			i->add_ref();
			const T * res = i->get();
			if (front) {
				//move the object in the beginning of the list
				_list.push_front(list_elem_t());
				_list.front() = *i;
				_list.erase(i);
			}
			return res;
		}
		return 0;
	}

	///unlocks object previously locked by get()
	void release(const key_type & key)
	{
		list_t::iterator i;
		i = std::find(_list.begin(), _list.end(), key);
		if (i == _list.end()) 
			throw std::runtime_error("bad release");
		i->release();
		if (i->free()) {
			if (_rest_resources < 0) {
				_rest_resources += i->get()->resource();
				_list.erase(i);
			}
		}
	}

private:
	void free_not_find_room()
	{
		list_t::iterator r = _list.end();
		if (r != _list.begin()) {
			--r;
			for (;;) {
				if (_rest_resources >= 0)
					break;
				list_t::iterator x = r--;
				if (x->free()) {
					_rest_resources += x->get()->resource();
					_list.erase(x);
				}
				if (x == _list.begin())
					break;
			}
		}
	}

private:
	typedef lru_elem_ptr<T>			list_elem_t;
	typedef std::list<list_elem_t>	list_t;

	resource_type	_total_resources;
	resource_type	_rest_resources;
	list_t			_list;
};

} //namespace xtd

#endif //_lru_h_
